﻿#pragma once
#include "Index.h"

class IMaxScoreAfterNOperations
{
public:
    /**
     * N次操作后的最大分数和.
     * https://leetcode.cn/problems/maximize-score-after-n-operations
     * 位运算 数组 数学 动态规划 回溯 状态压缩 数论
     *
     * 给你nums，它是一个大小为2*n的正整数数组。你必须对这个数组执行 n 次操作。
     * 在第 i 次操作时（操作编号从 1 开始），你需要：
     * 选择两个元素 x 和 y 。
     * 获得分数 i * gcd(x, y) 。
     * 将 x 和 y 从 nums 中删除。
     * 请你返回 n 次操作后你能获得的分数和最大为多少。
     * 函数 gcd(x, y) 是 x 和 y 的最大公约数。
     */
    virtual int maxScore(std::vector<int>& nums) = 0;
};

class MaxScoreAfterNOperations
{
public:
    class Solution
    {
    public:
        int maxScore(std::vector<int>& nums)
        {
            if (nums.empty())
                return 0;
            numsSize = nums.size();
            _preCalcGCD.clear();

            for (int i = 0; i < numsSize - 1; ++i)
                for (int j = i + 1; j < numsSize; ++j)
                {
                    _preCalcGCD[i][j] = gcd(nums[i], nums[j]);
                    //std::cout<<"gcd["<<i<<","<<j<<"]="<<_preCalcGCD[i][j]<<std::endl;
                }


            _memo.clear();
            return dp(0x0, numsSize >> 1);
        }
    private:
        //辗转相除法求最大公约数
        int gcd(int a, int b)
        {
            if (a == 0 || b == 0)
                return a + b;
            const int maxer = std::max<>(a, b);
            b = a + b - maxer;
            a = maxer;

            int mod = a % b;
            while (mod != 0)
            {
                a = b;
                b = mod;
                mod = a % b;
            }
            return b;
        }

        std::string printBinary(int val)
        {
            std::string binary;
            for (int i = 30; i >= 0; --i)
                binary += (val & (1 << i)) == 0 ? '0' : '1';
            return binary;
        }
        int dp(int flag, int op)
        {
            if ((flag & ((1 << numsSize) - 1)) == ((1 << numsSize) - 1))
                return 0;
            else if (_memo.count(flag))
                return _memo[flag];

            int ans = 0;
            for (int i = 0; i < numsSize - 1; ++i)
            {
                if (flag & (1 << i))
                    continue;
                for (int j = i + 1; j < numsSize; ++j)
                {
                    if ((flag & (1 << j)))
                        continue;

                    flag |= (1 << i);
                    flag |= (1 << j);
                    ans = std::max<>(ans, dp(flag, op - 1) + op * _preCalcGCD[i][j]);
                    flag &= ~(1 << i);
                    flag &= ~(1 << j);
                }
            }

            //std::cout << "flag:" << printBinary(flag) << " ans:" << ans << std::endl;
            _memo[flag] = ans;

            return ans;
        }
    private:
        int numsSize;
        std::unordered_map<int, int> _memo;
        std::unordered_map<int, std::unordered_map<int, int>> _preCalcGCD;
    };
};

#ifdef DEV_TEST
#include <gtest/gtest.h>
TEST(MaxScoreAfterOperationsTest, maxScore)
{
    MaxScoreAfterNOperations::Solution s;
    {
        std::vector<int> nums = { 1,2 };
        EXPECT_EQ(s.maxScore(nums), 1);
    }
    {
        std::vector<int> nums = { 3,4,6,8 };
        EXPECT_EQ(s.maxScore(nums), 11);
    }
    {
        std::vector<int> nums = { 1,2,3,4,5,6 };
        EXPECT_EQ(s.maxScore(nums), 14);
    }
    {
        std::vector<int> nums;
        FormatedUtil::parseFormated(nums, "[773274,313112,131789,222437,918065,49745,321270,74163,900218,80160,325440,961730]");
        EXPECT_EQ(s.maxScore(nums), 3032);
    }
    {
        std::vector<int> nums;
        FormatedUtil::parseFormated(nums, "[171651,546244,880754,412358]");
        EXPECT_EQ(s.maxScore(nums), 60);
    }
}
#endif